from typing import *
from heapq import heappop, heappush


class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        m, n = len(moveTime), len(moveTime[0])
        time0 = [[0] * n for _ in range(m)]
        time1 = [[0] * n for _ in range(m)]
        q = [(0, 0, 0, 0)]
        while q:
            t, x, y, f = heappop(q)
            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if (tx := x + i) >= 0 and tx < m and (ty := y + j) >= 0 and ty < n:
                    if f == 0 and time0[tx][ty] == 0:
                        time0[tx][ty] = (
                            t + f + 1
                            if t > moveTime[tx][ty]
                            else moveTime[tx][ty] + f + 1
                        )
                        if tx == m - 1 and ty == n - 1:
                            return time0[tx][ty]
                        heappush(q, (time0[tx][ty], tx, ty, 1))
                    if f == 1 and time1[tx][ty] == 0:
                        time1[tx][ty] = (
                            t + f + 1
                            if t > moveTime[tx][ty]
                            else moveTime[tx][ty] + f + 1
                        )
                        if tx == m - 1 and ty == n - 1:
                            return time1[tx][ty]
                        heappush(q, (time1[tx][ty], tx, ty, 0))


class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        m, n = len(moveTime), len(moveTime[0])
        time = [[[0] * 2 for _ in range(n)] for _ in range(m)]
        q = [(0, 0, 0, 0)]
        while q:
            t, x, y, f = heappop(q)
            for i, j in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if (
                    (tx := x + i) >= 0
                    and tx < m
                    and (ty := y + j) >= 0
                    and ty < n
                    and time[tx][ty][f] == 0
                ):
                    time[tx][ty][f] = (
                        t + f + 1 if t > moveTime[tx][ty] else moveTime[tx][ty] + f + 1
                    )
                    if tx == m - 1 and ty == n - 1:
                        return time[tx][ty][f]
                    heappush(q, (time[tx][ty][f], tx, ty, f ^ 1))
